import java.util.HashMap;
import java.util.Map;


/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 *
 * Date: 2022-09-30
 * Time: 13:30
 */
public class Algorithm {
    private static final Map<Long,Long> map = new HashMap<>();
    // 递归实现 本质和斐波那契数列是一样的
    public static long jumpFloor(long n) {
        if(n == 0) { return 1;}
        if(n <= 2) { return n; }

        long pPre; // n-2;
        if(map.containsKey(n-2)) {
            pPre = map.get(n-2);
        } else {
            pPre = jumpFloor(n-2);
            map.put(n-2,pPre);
        }

        long pre; // n-1;
        if(map.containsKey(n-1)) {
            pre = map.get(n-1);
        } else {
            pre = jumpFloor(n-1);
            map.put(n-1,pre);
        }

        return pPre + pre;
    }
    public static void main(String[] args) {
        int k = 7;
        System.out.print("青蛙跳到第" + k + "级台阶有 ");
        System.out.print(jumpFloor(k));
        System.out.println(" 种跳法");
    }
}
